package com.itHsuSE.demo5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Hsu琛君珩
 * @version 1.0
 */
public class Test3 {
    public static void main(String[] args) {
        int[] candidates={2,3,7,6};
        int target=7;
        Test3 test3=new Test3();
        System.out.println(test3.combinationSum(candidates,target));
    }
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates,target,0,0);
        return result;
    }
    public void backtracking(int[] candidates,int target,int sum,int startIndex){
        if(sum>target){
            return;
        }
        if(sum==target){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<candidates.length;i++){
            if(sum+candidates[i]>target){
                break;
            }
            path.add(candidates[i]);
            sum+=candidates[i];
            backtracking(candidates,target,sum,startIndex);
            path.removeLast();
            sum-=candidates[i];
        }
    }
}
